package com.jack.leetcode.每日一题;

import java.util.ArrayList;
import java.util.List;

/***
 * @author zhangjie
 * @date 2020/4/29 20:09
 */
public class 山脉数组中查找目标值 {

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        a.add(1);
        a.add(2);
        a.add(3);
        a.add(5);
        a.add(4);
//        a.add(4);
//        a.add(3);
//        a.add(2);
//        System.out.println(findInMountainArray(3,a));
//        System.out.println(findInMountainArray(1,a));
//        System.out.println(findInMountainArray(5,a));
        System.out.println(findInMountainArray(4,a));
    }

    public static int findInMountainArray(int target, List<Integer> mountainArr) {
        int n = mountainArr.size();
        int left = 0;
        int right = n-1;
        int mid = (left+right)/2;
        while(left<mid){
            if(mountainArr.get(mid)>mountainArr.get(mid+1)){
                right = mid;
            }else{
                left = mid;
            }
            mid = (left+right)/2;
        }
        if(target == mountainArr.get(mid)){
            return mid;
        }
        int left1 = 0;
        int right1 = mid;
        int left2 = mid+1;
        int right2 = n-1;
        int mid1 = (left1+right1)/2;
        int mid2 = (right2+left2)/2;
        while(left1<=right1){
            if(target == mountainArr.get(mid1)){
                return mid1;
            }else if(target > mountainArr.get(mid1)){
                left1 = mid1+1;
            }else{
                right1 = mid1-1;
            }
            mid1 = (left1+right1)/2;
        }
        if(target == mountainArr.get(mid1)){
            return mid1;
        }

        while(left2<=right2){
            if(target == mountainArr.get(mid2)){
                return mid2;
            }else if(target > mountainArr.get(mid2)){
                right2 = mid2-1;
            }else{
                left2 = mid2+1;
            }
            mid2 = (left2+right2)/2;
        }
        return -1;
    }
}
